#include <iostream>
#include <iomanip>
#include <stack>
#include <vector>
#include <utility>

#define factor 100

using namespace std;

namespace SplayTree
{
	vector < int > leftSon, rightSon, par, key;
	stack < int > avail;
	int root = 0;

	int init()
	{
		leftSon.push_back(0);
		rightSon.push_back(0);
		par.push_back(0);
		key.push_back(0);
	}

	int g(const int x)
	{
		return (par[par[x]]);
	}

	int rotate(int y, int dir = 0){
		// if dir == 0 then rotateLeft
		// if dir == 1 then rotateRight
		int x = rightSon[y], z = par[y];
		if(dir)
			x = leftSon[y];
		if(z){
			if(leftSon[z] == y)
				leftSon[z] = x;
			else
				rightSon[z] = x;
		}
		if(dir == 0){
			rightSon[y] = leftSon[x];
			leftSon[x] = y;
			if(rightSon[y])par[rightSon[y]] = y;
		}
		else{
			leftSon[y] = rightSon[x];
			rightSon[x] = y;
			if(leftSon[y])par[leftSon[y]] = y;
		}
		par[x] = z;
		par[y] = x;
		return 0;
	}
	
	int splay(int x){
		while(par[x]){
			if(x == leftSon[par[x]]){
				if(!g(x))rotate(par[x], 1);
				else{
					if(par[x] == leftSon[g(x)]){
						rotate(g(x), 1);
						rotate(par[x], 1);
					}
					else{ // par[x] == rightSon[g(x)]
						rotate(par[x], 1);
						rotate(par[x]);
					}
				}
			}
			else{ // x == rightSon[par[x]]
				if(!g(x))rotate(par[x]);
				else{
					if(par[x] == rightSon[g(x)]){
						rotate(g(x));
						rotate(par[x]);
					}
					else{ // par[x] == leftSon[g(x)]
						rotate(par[x]);
						rotate(par[x], 1);
					}
				}
			}
		}
		return x;
	}
	
	int	accessItem(int i, int root){
		int last(root);
		if(!root)return root;
		while(key[last] != i){
			if(key[last] > i)
				if(leftSon[last])
					last = leftSon[last];
				else
					break;
			else
				if(rightSon[last])
					last = rightSon[last];
				else
					break;
		}
		return splay(last);
	}

	int join(int t1, int t2){
		if(!t1)return t2;
		int last (t1);
		while(rightSon[last])
			last = rightSon[last];
		splay(last);
		if(t2)par[t2] = last;
		rightSon[last] = t2;
		return last;
	}

	pair < int, int > split(int i, int root){
		/* left tree will contain  *
		 * elements with the key   *
		 * not greater than i,     *
		 * right tree will contain *
		 * other elements          */
		int NewRoot = accessItem(i, root);
		int tree1, tree2;
		if(key[NewRoot] <= i){
			tree2 = rightSon[NewRoot];
			rightSon[NewRoot] = 0;
			tree1 = NewRoot;
		}
		else{
			tree1 = leftSon[NewRoot];
			leftSon[NewRoot] = 0;
			tree2 = NewRoot;
		}
		return make_pair(tree1, tree2);
	}

	int insertItem(int i, int root){
		int last(root), prev(root);
		while(last && key[last] != i){
			cout << "last = " << last << " x[" << last <<  "] = " << key[last] << endl;
			prev = last;
			if(key[last] < i)
				last = rightSon[last];
			else
				last = leftSon[last];
		}
		if(!last){
			if(avail.empty()){
				int size = key.size() - 1, p = size;
				size = (size) ? ((size + 1) / 2) : factor;
				for(int i = 0; i < size; ++i){
					init();
					avail.push(++p);
				}
			}
			last = avail.top();
			avail.pop();
			par[last] = prev;
			leftSon[last] = rightSon[last] = 0;
			key[last] = i;
			if(key[prev] < i)
				rightSon[prev] = last;
			else
				leftSon[prev] = last;
		}
		return splay(last);
	}

	int deleteItem(int i, int root){
		int NewRoot = accessItem(i, root);
		if(key[NewRoot] == i){
			avail.push(NewRoot);
			par[leftSon[NewRoot]] = par[rightSon[NewRoot]] = 0;
			return join(leftSon[NewRoot], rightSon[NewRoot]);
		}
		return NewRoot;
	}
};
